/*
    * Copyright (C) 2007 The Guava Authors
    *
    * Licensed under the Apache License, Version 2.0 (the "License");
    * you may not use this file except in compliance with the License.
    * You may obtain a copy of the License at
    *
    * http://www.apache.org/licenses/LICENSE-2.0
    *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package com.google.common.collect;
  
  import static com.google.common.base.Preconditions.checkArgument;
  import static com.google.common.base.Preconditions.checkState;
  import static com.google.common.collect.CollectPreconditions.checkRemove;
  
  import com.google.common.annotations.GwtCompatible;
  import com.google.common.base.Objects;
  
  import java.io.Serializable;
  import java.util.Collection;
  import java.util.Iterator;
  import java.util.Map;
  import java.util.Set;
  
  import javax.annotation.Nullable;
  
  /**
   * A general-purpose bimap implementation using any two backing {@code Map}
   * instances.
   *
   * <p>Note that this class contains {@code equals()} calls that keep it from
   * supporting {@code IdentityHashMap} backing maps.
   *
   * @author Kevin Bourrillion
   * @author Mike Bostock
   */
  @GwtCompatible(emulated = true)
  abstract class AbstractBiMap<K, V> extends ForwardingMap<K, V>
      implements BiMap<K, V>, Serializable {
  
    private transient Map<K, V> delegate;
    transient AbstractBiMap<V, K> inverse;
  
    /** Package-private constructor for creating a map-backed bimap. */
    AbstractBiMap(Map<K, V> forward, Map<V, K> backward) {
      setDelegates(forward, backward);
    }
  
    /** Private constructor for inverse bimap. */
    private AbstractBiMap(Map<K, V> backward, AbstractBiMap<V, K> forward) {
      delegate = backward;
      inverse = forward;
    }
  
    @Override protected Map<K, V> delegate() {
      return delegate;
    }
  
    /**
     * Returns its input, or throws an exception if this is not a valid key.
     */
    K checkKey(@Nullable K key) {
      return key;
    }
  
    /**
     * Returns its input, or throws an exception if this is not a valid value.
     */
    V checkValue(@Nullable V value) {
      return value;
    }
  
    /**
     * Specifies the delegate maps going in each direction. Called by the
     * constructor and by subclasses during deserialization.
     */
    void setDelegates(Map<K, V> forward, Map<V, K> backward) {
      checkState(delegate == null);
      checkState(inverse == null);
      checkArgument(forward.isEmpty());
      checkArgument(backward.isEmpty());
      checkArgument(forward != backward);
      delegate = forward;
      inverse = new Inverse<V, K>(backward, this);
    }
  
    void setInverse(AbstractBiMap<V, K> inverse) {
      this.inverse = inverse;
    }
  
    // Query Operations (optimizations)
  
   @Override public boolean containsValue(@Nullable Object value) {
     return inverse.containsKey(value);
   }
 
   // Modification Operations
 
   @Override public V put(@Nullable K key, @Nullable V value) {
     return putInBothMaps(key, value, false);
   }
 
   @Override
   public V forcePut(@Nullable K key, @Nullable V value) {
     return putInBothMaps(key, value, true);
   }
 
   private V putInBothMaps(@Nullable K key, @Nullable V value, boolean force) {
     checkKey(key);
     checkValue(value);
     boolean containedKey = containsKey(key);
     if (containedKey && Objects.equal(value, get(key))) {
       return value;
     }
     if (force) {
       inverse().remove(value);
     } else {
       checkArgument(!containsValue(value), "value already present: %s", value);
     }
     V oldValue = delegate.put(key, value);
     updateInverseMap(key, containedKey, oldValue, value);
     return oldValue;
   }
 
   private void updateInverseMap(
       K key, boolean containedKey, V oldValue, V newValue) {
     if (containedKey) {
       removeFromInverseMap(oldValue);
     }
     inverse.delegate.put(newValue, key);
   }
 
   @Override public V remove(@Nullable Object key) {
     return containsKey(key) ? removeFromBothMaps(key) : null;
   }
 
   private V removeFromBothMaps(Object key) {
     V oldValue = delegate.remove(key);
     removeFromInverseMap(oldValue);
     return oldValue;
   }
 
   private void removeFromInverseMap(V oldValue) {
     inverse.delegate.remove(oldValue);
   }
 
   // Bulk Operations
 
   @Override public void putAll(Map<? extends K, ? extends V> map) {
     for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
       put(entry.getKey(), entry.getValue());
     }
   }
 
   @Override public void clear() {
     delegate.clear();
     inverse.delegate.clear();
   }
 
   // Views
 
   @Override
   public BiMap<V, K> inverse() {
     return inverse;
   }
 
   private transient Set<K> keySet;
 
   @Override public Set<K> keySet() {
     Set<K> result = keySet;
     return (result == null) ? keySet = new KeySet() : result;
   }
 
   private class KeySet extends ForwardingSet<K> {
     @Override protected Set<K> delegate() {
       return delegate.keySet();
     }
 
     @Override public void clear() {
       AbstractBiMap.this.clear();
     }
 
     @Override public boolean remove(Object key) {
       if (!contains(key)) {
         return false;
       }
       removeFromBothMaps(key);
       return true;
     }
 
     @Override public boolean removeAll(Collection<?> keysToRemove) {
       return standardRemoveAll(keysToRemove);
     }
 
     @Override public boolean retainAll(Collection<?> keysToRetain) {
       return standardRetainAll(keysToRetain);
     }
 
     @Override public Iterator<K> iterator() {
       return Maps.keyIterator(entrySet().iterator());
     }
   }
 
   private transient Set<V> valueSet;
 
   @Override public Set<V> values() {
     /*
      * We can almost reuse the inverse's keySet, except we have to fix the
      * iteration order so that it is consistent with the forward map.
      */
     Set<V> result = valueSet;
     return (result == null) ? valueSet = new ValueSet() : result;
   }
 
   private class ValueSet extends ForwardingSet<V> {
     final Set<V> valuesDelegate = inverse.keySet();
 
     @Override protected Set<V> delegate() {
       return valuesDelegate;
     }
 
     @Override public Iterator<V> iterator() {
       return Maps.valueIterator(entrySet().iterator());
     }
 
     @Override public Object[] toArray() {
       return standardToArray();
     }
 
     @Override public <T> T[] toArray(T[] array) {
       return standardToArray(array);
     }
 
     @Override public String toString() {
       return standardToString();
     }
   }
 
   private transient Set<Entry<K, V>> entrySet;
 
   @Override public Set<Entry<K, V>> entrySet() {
     Set<Entry<K, V>> result = entrySet;
     return (result == null) ? entrySet = new EntrySet() : result;
   }
 
   private class EntrySet extends ForwardingSet<Entry<K, V>> {
     final Set<Entry<K, V>> esDelegate = delegate.entrySet();
 
     @Override protected Set<Entry<K, V>> delegate() {
       return esDelegate;
     }
 
     @Override public void clear() {
       AbstractBiMap.this.clear();
     }
 
     @Override public boolean remove(Object object) {
       if (!esDelegate.contains(object)) {
         return false;
       }
 
       // safe because esDelgate.contains(object).
       Entry<?, ?> entry = (Entry<?, ?>) object;
       inverse.delegate.remove(entry.getValue());
       /*
        * Remove the mapping in inverse before removing from esDelegate because
        * if entry is part of esDelegate, entry might be invalidated after the
        * mapping is removed from esDelegate.
        */
       esDelegate.remove(entry);
       return true;
     }
 
     @Override public Iterator<Entry<K, V>> iterator() {
       final Iterator<Entry<K, V>> iterator = esDelegate.iterator();
       return new Iterator<Entry<K, V>>() {
         Entry<K, V> entry;
 
         @Override public boolean hasNext() {
           return iterator.hasNext();
         }
 
         @Override public Entry<K, V> next() {
           entry = iterator.next();
           final Entry<K, V> finalEntry = entry;
 
           return new ForwardingMapEntry<K, V>() {
             @Override protected Entry<K, V> delegate() {
               return finalEntry;
             }
 
             @Override public V setValue(V value) {
               // Preconditions keep the map and inverse consistent.
               checkState(contains(this), "entry no longer in map");
               // similar to putInBothMaps, but set via entry
               if (Objects.equal(value, getValue())) {
                 return value;
               }
               checkArgument(!containsValue(value),
                   "value already present: %s", value);
               V oldValue = finalEntry.setValue(value);
               checkState(Objects.equal(value, get(getKey())),
                   "entry no longer in map");
               updateInverseMap(getKey(), true, oldValue, value);
               return oldValue;
             }
           };
         }
 
         @Override public void remove() {
           checkRemove(entry != null);
           V value = entry.getValue();
           iterator.remove();
           removeFromInverseMap(value);
         }
       };
     }
 
     // See java.util.Collections.CheckedEntrySet for details on attacks.
 
     @Override public Object[] toArray() {
       return standardToArray();
     }
     @Override public <T> T[] toArray(T[] array) {
       return standardToArray(array);
     }
     @Override public boolean contains(Object o) {
       return Maps.containsEntryImpl(delegate(), o);
     }
     @Override public boolean containsAll(Collection<?> c) {
       return standardContainsAll(c);
     }
     @Override public boolean removeAll(Collection<?> c) {
       return standardRemoveAll(c);
     }
     @Override public boolean retainAll(Collection<?> c) {
       return standardRetainAll(c);
     }
   }
 
   /** The inverse of any other {@code AbstractBiMap} subclass. */
   private static class Inverse<K, V> extends AbstractBiMap<K, V> {
     private Inverse(Map<K, V> backward, AbstractBiMap<V, K> forward) {
       super(backward, forward);
     }
 
     /*
      * Serialization stores the forward bimap, the inverse of this inverse.
      * Deserialization calls inverse() on the forward bimap and returns that
      * inverse.
      *
      * If a bimap and its inverse are serialized together, the deserialized
      * instances have inverse() methods that return the other.
      */
 
     @Override
     K checkKey(K key) {
       return inverse.checkValue(key);
     }
 
     @Override
     V checkValue(V value) {
       return inverse.checkKey(value);
     }
   }
 }